package architect.datastructure;

/**
 * 循环链表
 *
 * @author guanxin
 * @date 2018/5/7 14:09
 */

public class CircularLinkedList {
    // 链表节点
    private class Node {
        Object item; // 节点元素
        Node prev;   // 上一节点
        Node next;   // 下一节点

        public Node() { }

        public Node(Object item) {
            this.item = item;
        }

        public Node(Object item, Node prev, Node next) {
            this.item = item;
            this.prev = prev;
            this.next = next;
        }
    }

    Node first;
    int size;

    public CircularLinkedList() { }

    public void checkIndex(int index) {
        if (index < 0) {
            try {
                throw new Exception("索引超界");
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    }

    public void add(Object o) {
        Node node = new Node(o);
        if (this.first == null) {
            this.first = node;
            node.prev = node;
            node.next = node;
        } else {
            Node prevNode = first.prev;
            node.prev = prevNode;
            node.next = first;
            first.prev = node;
            prevNode.next = node;
        }
        size++;
    }

    public Node getNode(int index) {
        checkIndex(index);
        Node node = first;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }

    public void add(int index, Object o) {
        checkIndex(index);
        Node originalNode = getNode(index);
        Node prevNode = originalNode.prev;
        Node node = new Node(o);
        node.prev = prevNode;
        node.next = originalNode;
        originalNode.prev = node;
        prevNode.next = node;
        size++;
    }

    public Object remove(int index) {
        checkIndex(index);
        Node originalNode = getNode(index);
        Node prevNode = originalNode.prev;
        Node nextNode = originalNode.next;
        prevNode.next = nextNode;
        nextNode.prev = prevNode;
        size--;
        return originalNode.item;
    }

    public void remove(Node node) {
        Node prevNode = node.prev;
        Node nextNode = node.next;
        prevNode.next = nextNode;
        nextNode.prev = prevNode;
        size--;
    }

    public void remove(Object o) {
        Node node = first;
        int i;
        for (i = 0; i < size; i++) {
            if (node.item.equals(o)) {
                break;
            }
            node = node.next;
        }
        remove(i);
        size--;
    }
}
